package com.zhang;

/**
 * @author ZhangJiXin
 * @Description 并查集抽象类
 * @date 2021/4/30 9:52
 */
public abstract class UnionFind {
    protected int[] parents;

    protected UnionFind(int capacity) {
        if (capacity < 0 ){
            throw new IllegalArgumentException("capacity must be >= 1");
        }
        parents = new int[capacity];
        for (int i = 0; i < parents.length; i++) {
            parents[i] = i;
        }
    }

    /**
     * 查找v所属的集合(根节点)
     * @Author ZhangJiXin
     * @Date 2021/4/30 9:55
     * @param v:
     * @return: int
     */
    protected abstract int find(int v);

    /**
     * 合并v1、v2所属的集合
     * @Author ZhangJiXin
     * @Date 2021/4/30 9:55
     * @param v1:
     * @param v2:
     * @return: void
     */
    protected abstract void union(int v1,int v2);

    /**
     * 检查v1、v2是否属于同一个集合
     * @Author ZhangJiXin
     * @Date 2021/4/30 9:56
     * @param v1:
     * @param v2:
     * @return: boolean
     */
    protected boolean isSame(int v1,int v2){
        return find(v1) == find(v2);
    }

    /**
     * 检查元素范围规范
     * @Author ZhangJiXin
     * @Date 2021/4/30 10:31
     * @param v:
     * @return: void
     */
    protected void rangeCheck(int v){
        if (v < 0 || v >= parents.length){
            throw new IllegalArgumentException("capacity must be >= 1");
        }
    }
}
